package com.ilancuo.datastructuresandalgorithmsinjava.ch05_link;

/**
 * Created by ilancuo on 2018/8/29.
 */
class SortedList1 {
    private LinkD first;

    public SortedList1() {
        first = null;
    }

    public SortedList1(LinkD[] linkArr) {
        first = null;
        for (int j = 0; j < linkArr.length; j++)
            insert(linkArr[j]);
    }

    public void insert(LinkD k) {
        LinkD previous = null;
        LinkD current = first;
        while (current != null && k.dData > current.dData) {
            previous = current;
            current = current.next;
        }
        if (previous == null)
            first = k;
        else
            previous.next = k;
        k.next = current;
    }

    public LinkD remove() {
        LinkD temp = first;
        first = first.next;
        return temp;
    }
}

public class ListInsertionSort {
    public static void main(String[] args) {
        int size = 10;
        LinkD[] linkArr = new LinkD[size];
        for (int j = 0; j < size; j++) {
            int n = (int) (Math.random() * 99);
            LinkD newLink = new LinkD(n);
            linkArr[j] = newLink;
        }
        System.out.print("Unsorted array: ");
        for (int j = 0; j < size; j++)
            System.out.print(linkArr[j].dData + " ");
        System.out.println();

        SortedList1 theSortedList = new SortedList1(linkArr);
        for (int j = 0; j < size; j++)
            linkArr[j] = theSortedList.remove();

        System.out.print("Sorted Array: ");
        for (int i = 0; i < size; i++) {
            System.out.print(linkArr[i].dData + " ");
        }
        System.out.println();
    }
}
